1278C - Berry Jam - CodeForces Solution

data structures dp greedy implementation *1700

Please click on ads to support us..

Python Code: 



for _ in range(int(input())):
    n=int(input())
    l=list(map(int, input().split()))
    a=l[:n]
    b=l[n:]
    d={}
    x=0
    y=0
    for i in range(n):
        if a[i]==1:
            x+=1
        else:
            y+=1 
        dif=x-y 
        d[dif]=i 
    ans=2*n
    x=0
    y=0
    for i in range(n-1,-1,-1):
        if b[i]==1:
            x+=1
        else:
            y+=1 
        dif=y-x 
        if dif in d:
            ans=min(ans, i+n-d[dif]-1)
            if 0 in d:
        ans=min(ans, n+n-d[0]-1)
        
            if x==y:
        ans=min(ans,n)
    l=l[::-1]
    a=l[:n]
    b=l[n:]
    d={}
    x=0
    y=0
    for i in range(n):
        if a[i]==1:
            x+=1
        else:
            y+=1 
        dif=x-y 
        d[dif]=i 
        x=0
    y=0
    for i in range(n-1,-1,-1):
        if b[i]==1:
            x+=1
        else:
            y+=1 
        dif=y-x 
        if dif in d:
            ans=min(ans, i+n-d[dif]-1)
            if 0 in d:
        ans=min(ans, n+n-d[0]-1)
        
            if x==y:
        ans=min(ans,n)
        print(ans)

C++ Code: 

#include <bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0)
#define endl '\n'
#define int long long
#define ar array<int, 2>
#define arr array<int, 3>
const int N = 2e5 + 5, M = 2 * N;
const int inf = 0x3f3f3f3f;
int mod = 998244353; //1e9+7;
int t, n, m, k;

signed main()
{
    ios;
#ifdef DEBUG
    freopen("../1.in", "r", stdin);
#endif
    // 那时候刷的可起劲了。这题。
    // 主要是1 2 换成-1  1 这样的设定。
    // 然后就是贪心的哈希。。和类似两数之和的两个集合的配对。。
    // 有点类似二分图。。
    cin >> t;
    while (t--)
    {
        cin >> n;
        vector<int> sum(2 * n + 1);
        map<int, int> mp;
        mp[0] = 0;
        for (int i = 1; i <= 2 * n; ++i)
        {
            int x;
            cin >> x;
            sum[i] = sum[i - 1] + (x > 1 ? -1 : 1);
            if (i <= n)
                mp[sum[i]] = i;
        }
        int ans = 2 * n;
        for (int i = n; i <= 2 * n; ++i)
        {
            int tmp = sum[i] - sum[2 * n];
            if (mp.count(tmp))
                ans = min(i - mp[tmp], ans);
        }
        cout << ans << endl;
    }
};


Comments

Submit
0 Comments
More Questions

1474E - What Is It
1335B - Construct the String
1004B - Sonya and Exhibition
1397A - Juggling Letters
985C - Liebig's Barrels
115A - Party
746B - Decoding
1424G - Years
1663A - Who Tested
1073B - Vasya and Books
195B - After Training
455A - Boredom
1099A - Snowball
1651D - Nearest Excluded Points
599A - Patrick and Shopping
237A - Free Cash
1615B - And It's Non-Zero
1619E - MEX and Increments
34B - Sale
1436A - Reorder
1363C - Game On Leaves
1373C - Pluses and Minuses
1173B - Nauuo and Chess
318B - Strings of Power
1625A - Ancient Civilization
864A - Fair Game
1663B - Mike's Sequence
448A - Rewards
1622A - Construct a Rectangle
1620A - Equal or Not Equal